Results: Algorithm 3

Tests

Levels tested: Extreme + x for x in [0,25,50,100,all] all implies L = Y, ie not defined by Yse.

We expect that q_stats increase in the number of subproblems (when Ys_is_Gs is removed).

## # A tibble: 9 × 5
## # Groups:   m [3]
##       m subset_global_method q_mean q_unknown_mean instance_count
##   <dbl> <chr>                 <dbl>          <dbl>          <int>
## 1     2 m|m                  0.261          0.0347            288
## 2     2 ul|u                 0.386          0.113             144
## 3     2 u|u                  0.164          0.0706             72
## 4     3 m|m                  0.168          0.0167           1500
## 5     3 ul|u                 0.493          0.209             500
## 6     3 u|u                  0              0                 500
## 7     4 m|m                  0.189          0.0356           6656
## 8     4 ul|u                 0.394          0.130            3842
## 9     4 u|u                  0.0697         0.0248           4467

Suprisingly we find that \(q^M\) decreases in the number of subproblems? (Maybe because only a subset of all instances have been run? instances with many known vectors not run for m=4).

Effects of lower bound:

We here consider the effect of assumptions on the lower bound set. We compare the cases where all vectors of the

We consider only the \(\bar q^s\) values where the lower bound used in ALG3_pair. In the above table

We now compare the q_stats for different levels of known vectors \(\frac{|\hat Y^s|}{|Y^s|}\). To limit the number of plots we split the ration of known vectors if other subproblems into intervals of 25%.

Check the size of RGS relative to MGS

\[ \frac{|\hat G^s|}{|G^s|} \]

Now we consider the number of removed vectors relative to the subproblem size:

Here we see a trend that a higher proportion of redundant vectors are identified/removed when more vectors are known.

Section text

For reference: ALG3_Pair

In this section, we wish to answer the research question: “How many redundant vectors can be identified using [ALG3_pair]”.

When solving MSPs, one can use bound sets of subproblems along with theorem [X] to decrease the search area for minimum generator vectors of the subproblems. ALG3_pair uses bound set information of subsets to identify redundant vectors of subproblems. We will use the result of ALG3_pair as a proxy, of how many vectors one can expect to remove from the search areas of subproblems using theorem [X].

We want to see how many of the redundant vectors $Y^s G^s $ that can be identified by the algorithm [ref alg3_pair] using lower and upper bound sets \(L^s, U^s\) for each subproblem. In the following, \(G\) denotes any minimum generator set and \(\hat{G}\) denotes the generator set returned by [ALG3_pair].

We expect, that the number of identified redundant vectors increase in the quality of the bound sets. To test this hypothesis, we will define a variaty of lower and upper bound sets for each instance used in [MGS study]. For each subproblem we will generate subsets of nondominated subproblem vectors \(\hat Y^s \subseteq Y^s_N\) and use these to define bound sets. Motivated by the fact that all supported extreme vectors of subproblems must be part of any generator set, and hence must be computed we generate bound sets which always assume that these vectors are known in the subproblems. We will compare two types of lower bound sets: \(L^s = conv(Y_{se}^s)_N\) and \(L^s = Y^s_N\). Given a subset \(\hat{Y}^s \subseteq Y^s_N\) we will define an upper bound set using the local nadir vectors of \(\hat Y^s\). \([U(\hat Y) = \bigcup_{i}{(y^{i+1}_1,y^i_2)}]\).

Given a \(\lambda^s \in [0,1]\) we will define a subset of partial level \(\lambda^s\) as one of the smallest subsets \(\hat{ Y^s} \subseteq Y^s\) which satisfies \(Y_{se}^s \subseteq \hat Y^s\) and $|Y^s| |Y_{se}^s| + |Y^s Y_{se}^s| $. i.e. we define a partially known set of partial level \(\lambda^s\) as a subset of \(Y^s\) which contains all extreme supported vectors along with \(\lambda^s\) of the remaining vectors of \(Y^s\). In our experiments we choose a random subset which satisfies the condition. We create instances for different levels of \(\lambda^s \in \{0, 25\%, 50\%, 75\%, 100\%\}\) for all subproblems.

Total instances: for a problem of size \(m\) we get \(5^m\) instances of varying partial levels, when creating all possible partial level combinations.

Total subproblems: 27388

Total instances: 7438.

TODO (check all instances are solved).

For each instance and subproblem \(s \in S\), we define the measure \(\bar q^s = \frac{|Y^s|- |\hat G^s|}{|Y^s|-|G^s|}\) as the proportion of redundant vectors in \(Y^s \setminus G^s\) which are identified by the algorithm [alg3_pair]. In case \(Y^s = G^s\), we define \(\bar q^s = 1\) as all redundant vectors in \(\emptyset\), are identified. (We might only show statistics where \(|Y^s| \neq |G^s|\)). To show the number of redundant vectors that are identified we consider the statistic \(\bar t^s = \frac{|Y^s|-|\hat G^s|}{|Y^s|}\), i.e. the amount of vectors identified relative to the number of subproblem vectors.

OBS: The line averages are over all subproblems, not instances. That is, instances with m=4 have higher weight than instances with m = 2. There are more instances per filename (MSP instance) and more subproblems per instance.

In plot [above] we see how the proportion of redundant vectors identified by [alg3_pair] (\(\bar q^s\)) varies for different partial levels \(\lambda^s\) of both a subproblem and the average partial level of the other subproblems for the same instance \(\bar \lambda^{-s} = \frac{1}{|S|-1}\sum_{s' \neq s}\lambda^{s'}\).

We find that \(\bar q^s\) increases in the partial level \(\lambda^s\) and in \(\bar \lambda^{-s}\) for the methods \(ul|u\) and \(m|m\).

For subsets \(s\) of type \(ul|u\) with \(\lambda^s = 0\), the upper bound consists of only the nadir point which is a bad approximation of \(Y_N^s\) resulting in low \(\bar q^s\) values. Increasing \(\lambda^s\) and adding vectors to \(\hat Y^s\) improves the quality of the upper bound which in turn increases the \(\bar q^s\) values. This explains the initial jump in the \(\bar q^s\) values for \(ul|u\) subproblems which does not appear for \(m|m\) instances where the initial approximation are likely to include several vectors and not only the subproblem nadir vectors.

\(l|l\) and \(ul|l\) are special cases where all redundant vectors are identified only because no redundant vectors exist. Similarly for most instances \(u|u\) no redundant vectors are identified apart from the case where all other subsets are fully known and the stronger lower bound is used.

In the final row of [above plot] we compare the two cases where the lower bound sets of the other subproblems are \(L^s = conv(Y_{se}^s)_N\) [100] or \(L^s = Y^s_N\) [all]. Here we see a significant incease in \(\bar q^s\) values when using the better lower bound. In our experiments we only consider two lower bound sets but one could also consider lower bound sets based on the extreme supported solutions and remove known empty search regions by adding local nadir vectors.

Same plot as above, but now we consider the relative size of the known subsets \(\frac{|\hat Y^s|}{Y_N^s}\) instead of the partial level (\(\lambda^s\)). Again we see that \(\bar q^s\) increases in both the number of known vectors.

In the following, we plot the proportion of vectors removed from subproblems (\(\bar t^s\)).

(Maybe add the above lines in the first plot as dashed lines?)

In the plot [above], we plot the number of redundant vectors removed from each subproblem relative to the subproblem size. Here it is clear that no redundant vectors are found in the cases \(ul|l\) and \(u|u\).

Note: The [alg3_pair] is ineffective at identifying the redundant vectors in the \(u|u\) case, only being able to remove vectors when all other subsets are known and using the better lower bound sets. We know from the above section [MGS empirical] that there are relatively many for \(p=2\) and \(m > 2\). Instead of the pairwise approach taken in [alg3_pair], perhaps a sequential approach will prove effective for these instances.

Lower bound sets

In the table [ref], we summarize results for \(m=2, p=2\) where \(\hat Y^2 = Yn^2\), comparing the effects of the different lower bounds \(L^s = Y_N\) and \(L^s = conv(Y^s_N)\). This shows that the improved lower bound set obtained using the assumption, significantly improves the number of redundant vectors that can be identified by [ref alg3_pair].

Other plots (removed unknown vectors)

Compare removed \(Y^s \setminus \hat G^s\) and removed unknown \(Y^s \setminus \hat G^s \setminus \hat Y^s\).

Same plots as above, but statistics for unknown \((U)\) vectors. \[\bar q_U^s = \frac{|Y^s \setminus \hat G^s \setminus \hat Y^s|}{|Y^s|-|G^s|}\] \[\bar t_U^s = \frac{|Y^s \setminus \hat G^s \setminus \hat Y^s|}{|Y^s|}\]

(dashed lines shows \(removed\_unkown / |Y_N^s|\))

The relative plot from above: